package com.hqq.exercise.cal;

/**
 * PrintToMaxOfNDigit 打印1到最大的n位数
 * 题目描述:
 * 输入数字n 按照顺序打印出从1到最大的n位进制数
 * 考点: 如果n太大使用基本类型是无法保存这么大的数的ORZ... 考虑使用数组
 * 输入样例:
 * 3
 * 输出样例:
 * 1,2,3,4,5..999
 * Created by heqianqian on 2017/8/10.
 */
public class PrintToMaxOfNDigit {

    public static void printToMaxOfNDigit(int number) {
        if (number < 1) {
            throw new RuntimeException("The input number must larger than 0");
        }
        //创建一个数组用于存放值
        int[] array = new int[number];
        printOneToNthDigits(0, array);
    }

    /**
     * 输入数字n 按照顺序打印出从1到最大的n位十进制数
     *
     * @param n     处理的是第n个元素 从n开始计数
     * @param array 存放结果的数组
     */
    private static void printOneToNthDigits(int n, int[] array) {
        if (n >= array.length) {//说明所有的数据排列选择已经处理完了
            printArray(array);
        } else {
            for (int i = 0; i <= 9; i++) {
                array[n] = i;
                printOneToNthDigits(n + 1, array);
            }
        }
    }

    /**
     * 输入数组的元素 从左到右 从第一个非0值开始输出到最后的元素
     *
     * @param array 要输出的数组
     */
    private static void printArray(int[] array) {
        //找第一个非0的元素
        int index = 0;
        while (index < array.length && array[index] == 0) {
            index++;
        }
        //从第一个非0值开始到输出最后的元素
        for (int i = index; i < array.length; i++) {
            System.out.print(array[i]);
        }
        //条件成立说明数组中有非0元素 所以需要换行
        if (index < array.length) {
            System.out.println();
        }
    }

    /**
     * 第二种方法，比上一种少用内存空间
     */
    public static void printOneToNthDigits2(int n) {
        //输入值必须大于0
        if (n < 1) {
            throw new RuntimeException("The input number must larger than 0");
        }
        //创建一个长度为n的数组
        int[] array = new int[n];
        //为数组元素赋初始值
        for (int i = 0; i < array.length; i++) {
            array[i] = 0;
        }
        //求结果 如果最高位没有进位就一直进行处理
        while (addOne(array)==0){
            printArray(array);
        }
    }

    /**
     * 对arr表示的数组的最低位加1 arr中的每个数都不能超过9不能小于0，每个位置模拟一个数位
     * @param array 待加数组
     * @return 判断最高位是否有进位，如果有进位就返回1，否则返回0
     */
    private static int addOne(int[] array) {
        //保存进位值 每次最低位加1
        int carry = 1;
        int index = array.length;
        do{
            //指向上一个处理位置
            index--;
            //处理位置的值加上进位的值
            array[index]+=carry;
            //求处理位置的进位
            carry = array[index]/10;
            //求处理位置的值
            array[index] %= 10;
        }while (carry!=0&&index>0);
        //如果index=0说明已经处理了最高位 carry>0说明最高位有进位，返回1
        if (carry>0 && index == 0){
            return 1;
        }
        //无进位返回0
        return 0;
    }
}
